package com.atcumt.lcSolution;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 单调队列
 */
public class LC2 {

    // 滑动窗口最大值
    // [1  3  -1] -3  5  3  6  7       3
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[n - k + 1]; // 存储滑动窗口最大值

        if (n < k || nums == null) {
            return new int[0];
        }
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.getLast()]) {
                deque.removeLast();
            }
            deque.addLast(i); // nums[i]小于队尾元素

            if (deque.getFirst() <= i - k) {
                deque.removeFirst(); // 维护滑动窗口 [i - k, i]
            }

            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.getFirst()]; // 输出结果
            }
        }
        return res;
    }

    /**
     * 柱状图中的最大矩形
     * 准备单调递增栈存放数组下标，这样可以从栈顶找到左边第一个比自己小的下标，
     * 这样从当前下标出发到第一个比自己小的柱子的下标就是矩形面积的宽度，然后在乘当前柱子的高度就是面积，
     * 如果当前柱子大于栈顶的下标对应的柱子高度，就入栈，否则不断出栈，计算栈顶的柱子所能形成的矩形面积，更新最大矩形面积
     */
    public int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        int n = heights.length;
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            if (stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.push(i); // 当前下标加入栈
            } else {
                int top = -1;
                while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                    top = stack.pop();
                    maxArea = Math.max(maxArea, heights[top] * (i - top));
                }
                heights[top] = heights[i]; // 更新 heights[top]
                stack.push(top);
            }
        }
        // i = n 边界单独考虑
        while (!stack.isEmpty()) {
            int top = stack.pop();
            maxArea = Math.max(maxArea, heights[top] * (n - top));
        }
        return maxArea;
    }

    /**
     * 最大矩形
     *
     * 从第一行到第n行形成的柱状图可以利用单调栈，循环每一行，计算以这一行为底的柱状图最大面积，更新最大矩形面积
     */
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }
        int col = matrix[0].length;
        int[] heights = new int[col + 1];
        heights[col] = -1; // 初始化
        int maxArea = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
            }
            maxArea = Math.max(maxArea, largestRectangleArea(Arrays.copyOf(heights, col + 1)));
        }
        return maxArea;
    }
}
